package demo.DataStrucAndAlgo.Easy_pritice;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Auther: hjy(lc))
 * @Date: 2022/8/30-08-30-18:08
 * @Description：demo.DataStrucAndAlgo.Easy_pritice
 */
public class bracket_Gener {
    public static void main(String[] args) {
        int[] nums = {2,2,4,1,42,4};

        System.out.println(generateParenthesis(3));
    }
    public List<String> generateBracket(int n){
        List<String> ans = new ArrayList<>();
        if(n == 0){
            ans.add("");
        }else{
            for(int a = 0; a < n; a++){
                for (String left : generateBracket(a)) {
                    for (String right : generateBracket((n - 1 - a))) {
                        ans.add("(" + left + ")" + right);
                    }
                }
            }
        }
        return ans;
    }

    public static List<String> generateParenthesis(int n) {
        if(n == 0){
            return null;
        }
        LinkedList<LinkedList<String>> result = new LinkedList<LinkedList<String>>();
        LinkedList<String> list = new LinkedList<>();
        list.add("");
        result.add(list);    //0
        list = new LinkedList<>();
        list.add("()");      //1
        for(int i = 2; i <= n; i++){
            list = new LinkedList<>();
            for(int j = 0; j < i; j++){
                LinkedList<String> left = result.get(j);
                LinkedList<String> right = result.get(i-j-1);
                for (String s : left) {
                    String str = null;
                    for (String s1 : right) {
                        str = "(" + s + ")" + s1;
                        list.add(str);
                    }
                }
            }
            result.add(list);
        }
        return result.get(n);
    }
}
